/*18. 四数之和
难度：中等
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 
（若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案 。
*/





#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;



// 默认nums为升序排好
void threeSum(int n,vector<vector<int>>& res,vector<int>& nums,int target=0) 
{
    if(nums.size()<3)
        return ;   
    sort(nums.begin(),nums.end());  
    if(target<=0&&nums[0]>0)
        return ;
    if(target>0&&nums[nums.size()-1]<=0)
        return ;
    for(int i=0;i<nums.size()-2;i++)
    {
        if(target<=0&&nums[i]>0)
            break;
        if(i>0&&nums[i]==nums[i-1])
            continue;
        int left = i + 1;
        int right = nums.size() - 1;
        while(left<right)
        {
            long long calculate = static_cast<long long>(nums[i]) + nums[left] + nums[right] - target;
            if(calculate>0)
                right--;
            else if(calculate<0)
                left++;
            else
            {
                res.push_back({n,nums[i],nums[left],nums[right]});
                while(right>2&&nums[right]==nums[right-1]){right--;}
                while(left<nums.size()-3&&nums[left]==nums[left+1]){left++;}//需要注意数组的范围
                right--;
                left++;
            }
        }
    }     
}


vector<vector<int>> fourSum(vector<int>& nums, int target) 
{
    vector<vector<int>> res;
    if(nums.size()<4)
        return res;   

    sort(nums.begin(),nums.end());
    
    if(target<=0&&nums[0]>0)
        return res;
    if(target>0&&nums[nums.size()-1]<=0)
        return res;

    for (int i = 0; i < nums.size() - 3;i++)
    {
        if(target<=0&&nums[i]>0)
            break;
        if(i>0&&nums[i]==nums[i-1])
            continue;
        vector<int> slice = vector<int>(nums.begin()+i+1, nums.end());
        threeSum(nums[i],res,slice,target-nums[i]);
    }
    return res;
}


int main(void)
{
    vector<int> nums = {0,0,0,1000000000,1000000000,1000000000,1000000000};
    vector<vector<int>> res;
    res=fourSum(nums, 1000000000);
    // res.push_back({0,1,2});
    // threeSum(1,res,nums,0);
    for(int i=0;i<res.size();i++)
    {
        for(int j=0;j<res[i].size();j++)
        {
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}